import java.math.*;
public class GeoTool {
	
	// Using Ray casting algorithm
	public static boolean ifInPolygon(Point p , Polygon m){
		// The point should have overlaps in both x coordinates and y coordinates with polygon
		
		double minX = m.outring[0].x;
		double minY = m.outring[0].y;
		double maxX = m.outring[0].x;
		double maxY = m.outring[0].y;
		
		for( Point polyPoint : m.outring){
			//if(p.id == 4 && m.id==12 && m.timestamp==12) System.out.println(polyPoint.x+" "+polyPoint.y);
			if(polyPoint.x<minX) minX = polyPoint.x;
			if(polyPoint.x>maxX) maxX = polyPoint.x;
			if(polyPoint.y<minY) minY = polyPoint.y;
			if(polyPoint.y>maxY) maxY = polyPoint.y;
		}
		
		if(p.x<minX || p.x>maxX || p.y<minY || p.y>maxY) return false;
		
		
		// Make a ray pp2 starting from p 
		Point p2 = new Point(Double.MAX_VALUE,p.y);
		int intersects=0;
		
		for( int i =0 ; i<m.outring.length-1 ; i++ ){
			if(ifIntersect(p,p2,m.outring[i],m.outring[i+1])) intersects++;
		}
		if(m.inring!=null){
			for( int i =0 ; i<m.inring.length-1 ; i++ ){
				if(ifIntersect(p,p2,m.inring[i],m.inring[i+1])) intersects++;
			}
		}
		if( intersects%2==0 ) return false;
		else return true;
	}
	
	public static boolean ifWithinPolygon(Point p , Polygon m, int distance){
		if(ifInPolygon(p,m)){
			if(distance>0) return true;
			else return false;
		}
		else{
			double closestDist = Double.MAX_VALUE;
			for( Point p1 : m.outring ){
				double dist;
				if( ( dist = java.awt.geom.Point2D.distance(p.x, p.y, p1.x, p1.y))<closestDist ) closestDist = dist;
			}
			closestDist = Math.round(closestDist*100.0)/100.0;
			if( closestDist < distance ) return true;
			else return false;
		}
	}
	 
	
	public static boolean ifIntersect(Point a1,Point a2,Point b1,Point b2){
		// If two lines do not have overlap in y coordinate, then they can't intersect
		if(ifOverlap(a1.y,a2.y,b1.y,b2.y)==false) return false;
		// If two lines do not have overlap in x coordinate, then they can't intersect
		else if(ifOverlap(a1.x,a2.x,b1.x,b2.x)==false) return false;
		
		// Check if two line segments intersect
		// If Both lines are horizontal or vertical, they don't intersect
		if(a1.x == a2.x && b1.x==b2.x) return false;
		else if(a1.y==a2.y && b1.y == b2.y) return false;
		// If one is horizontal and the other is vertical, they intersect
		else if( a1.x==a2.x && b1.y==b2.y) return true;
		else if( a1.y==a2.y && b1.x==b2.x) return true;
		
		return java.awt.geom.Line2D.linesIntersect(a1.x, a1.y, a2.x, a2.y, b1.x, b1.y, b2.x, b2.y);
		/*
		// If a1a2 is vertical
		if(a2.y==a1.y){
			//Given y = a1.y + t(a2.y - a1.y)
			// x = a1.x + t(a2.x - a1.x)
				double t1 = (a1.y-b1.y)/(b2.y-b1.y);
				double t2 = (a2.y-b1.y)/(b2.y-b1.y);
				if((b1.x+t1*(b2.x-b1.x)-a1.x)*(b1.x+t2*(b2.x-b1.x)-a2.x)<=0) return true;
				else return false;	
		}
		else{
		//Given y = a1.y + t(a2.y - a1.y)
		// x = a1.x + t(a2.x - a1.x)
			double t1 = (b1.y-a1.y)/(a2.y-a1.y);
			double t2 = (b2.y-a1.y)/(a2.y-a1.y);
			//System.out.println(t1+" "+t2);
			if((a1.x+t1*(a2.x-a1.x)-b1.x)*(a1.x+t2*(a2.x-a1.x)-b2.x)<=0) return true;
			else return false;
		}
		*/
		
	}
	
	// One 1D coordinate, if two line segments overlap
	public static boolean ifOverlap(double x1,double x2, double y1, double y2){
		// if right point of line segment of x1x2 is to the left of the left point of segment y1y2, there is no overlap
		if(Math.max(x1,x2) < Math.min(y1,y2) ) return false;
		// if right point of line segment of y1y2 is to the left of the left point of segment x1x2, there is no overlap
		else if(Math.max(y1,y2) < Math.min(x1,x2) ) return false;
		return true;
	}
	public static void main(String[] args){
		Point p1 = new Point(Double.MAX_VALUE,4.2);
		Point p2 = new Point(7.5,Double.MIN_VALUE);
		Point q1 = new Point(Double.MIN_VALUE,-9.8);
		Point q2 = new Point(9.8,Double.MAX_VALUE);
		
		long startTime = System.currentTimeMillis();
		for(int i = 0 ; i < 10000000 ; i++){
			GeoTool.ifIntersect(p1, p2, q1, q2);
		}
		 long stopTime = System.currentTimeMillis();
	     long elapsedTime = stopTime - startTime;
	      System.out.println(elapsedTime);
	     
	    startTime = System.currentTimeMillis();
		for(int i = 0 ; i < 10000000 ; i++){
			java.awt.geom.Line2D.linesIntersect(p1.x, p1.y, p2.x, p2.y, q1.x, q1.y, q2.x, q2.y);
		}
		stopTime = System.currentTimeMillis();
	    elapsedTime = stopTime - startTime;
	    System.out.println(elapsedTime);
	    
	   
	}
}
